package com.kehao.newcoder;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class NC54Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        Arrays.sort(num);
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        Map<Integer,Integer> numIndexMap = new HashMap<>();
        for (int i = 0; i < num.length; i++) {
            numIndexMap.put(num[i],i);
        }
        for (int i = 0; i < num.length-2; i++) {
            if(num[i]>0){
                break;
            }
            if(i>0&&num[i]==num[i-1]){
                continue;
            }
            for (int j = i+1; j < num.length-1; j++) {
                int partSum = num[i] + num[j];
                if(partSum>0){
                    break;
                }
                if(j>i+1&&num[j]==num[j-1]){
                    continue;
                }
                if(numIndexMap.containsKey(-partSum)){
                    int index = numIndexMap.get(-partSum);
                    if(index>j){
                        ArrayList<Integer> item = new ArrayList<>();
                        item.add(num[i]);
                        item.add(num[j]);
                        item.add(num[index]);
                        result.add(item);
                    }
                }
            }
        }
        return result;
    }

    @Test
    public void test(){
        threeSum(new int[]{0,0});
    }
}
